/*
 * =====================================================================================
 *
 *       Filename:  graph.c
 *
 * =====================================================================================
 */

#include "graph.h"
#include "list.h"
#include "queue.h"
#include "zmalloc.h"
#include "math_bit.h"
#include <stdlib.h>
#include <string.h>

#define HASH_FUNCTION(buf,len,seed) Murmurhash64A(buf, len, seed)


Graphs *graph_create(uint32_t gtype,unsigned v_slot,unsigned e_slot)
{
        int i;
	uint32_t max_slots;

	/* TODO: adding union now parameter number maximum nodes in a graph  */
	Graphs *self = (Graphs *)calloc(1, sizeof(Graphs));
        self->graph_type = gtype;
        self->v_slots = ROUND_UP32(v_slot);
        self->e_slots = ROUND_UP32(e_slot);
        self->free = free;

	switch(gtype) {
	case simple:
	    self->vertex = listCreate();
	    self->edge = listCreate();

	    self->vertex->free = self->edge->free = free;
	    break;

	case hash_vertex:
	case hash_source:
	case hash_dest:

	    max_slots = ROUND_UP32(v_slot)+1;
	    self->hash_v = (list **)calloc(max_slots,sizeof(list *));
	    max_slots = ROUND_UP32(e_slot)+1;
	    self->hash_e = (list **)calloc(max_slots,sizeof(list *));

	       for(i = 0 ; i<=self->v_slots; i++ ) {
		  self->hash_v[i] = listCreate();
		  self->hash_v[i]->free = free; 
		  }

	       for(i = 0 ; i<=self->e_slots; i++ ) {
		  self->hash_e[i] = listCreate();
		  self->hash_e[i]->free = free; 
		  }
	    
	    break;

	default:
	    /* Error of setting graph initial creating */
	    break;
	}

	return self;
}

void graph_set_vh_func(Graphs *graph,void (*hashfunc)(void *)) {
      graph->vh_func = hashfunc;
      return;
}


void graph_set_eh_func(Graphs *graph,void (*hashfunc)(void *)) {
      graph->eh_func = hashfunc;
      return;
}

void graph_release(Graphs *graph)
{

   uint32_t i;

   do {

   if (graph == NULL)  break;

   switch(graph->graph_type) {

	case simple:
		listRelease(graph->vertex);
		listRelease(graph->edge);
		free(graph);
		break;	   
        default:
	  
	  for(i=0;i<=graph->v_slots;i++)
	       listRelease(graph->hash_v[i]);
	  for(i=0;i<=graph->e_slots;i++)
	       listRelease(graph->hash_e[i]);
	  graph->free(graph->hash_v);
	  graph->free(graph->hash_e);
	  break;
	 }

   } while(0);

   return;
}

int graph_IsEmpty(Graphs *graph)
{  
   uint32_t count=0;
   
   do {
      if ( graph == NULL ) break;
      count = listLength(graph->vertex)*listLength(graph->edge) ; 
	
   } while(0);

   return(count);
}

Graph_node *graph_node_create() {
    Graph_node *self; 
    self = (Graph_node *)zcalloc(sizeof(*self)); 
    return(self);
}

Graph_link *graph_link_create() {
    Graph_link *self; 
    self = (Graph_link *)zcalloc(sizeof(*self)); 
    return(self);
}

void graph_node_release(Graph_node *vertex, void vfree(void *ptr), void nfree(void *ptr)) {
    vfree(vertex->value);    
    nfree(vertex);    
    return;
}

void graph_edge_release(Graph_link *edge, void vfree(void *ptr), void nfree(void *ptr)) {
    vfree(edge->value);    
    nfree(edge);    
    return;
}

void graph_add_vertex(Graphs *graph, Graph_node *vertex) {
    listAddNodeTail(graph->vertex, vertex);
    return;
}

void graph_add2vertex(Graphs *graph, void *data) {
    Graph_node *self = graph_node_create();
    self->value = data;
    listAddNodeTail(graph->vertex, self);
    return;
}

void graph_insert_vertex(Graphs *graph, Graph_node *vertex,
		 int (*cmp) (const void *, const void *)) {
    list_binsert(graph->vertex, vertex, cmp );
    return;
}

void graph_insert2vertex(Graphs *graph, void *data,
		 int (*cmp) (const void *, const void *)) {
    Graph_node *self = graph_node_create();
    self->value = data;
    graph_insert_vertex(graph, self, cmp );
    return;
}

void graph_del_node(Graphs *graph, Graph_node *node,
	       int(*ncmp)(const void *,const void *)) {
      list_bDel_key(graph->vertex, node, ncmp);
      return;
   }

void graph_bDel_node(Graphs *graph, Graph_vertex *vertex,
	       int(*ncmp)(const void *,const void *)) {
      list_bDel(graph->vertex, vertex, ncmp);
      return;
   }


void graph_add_edge(Graphs *graph, Graph_link *edge) {
    listAddNodeTail(graph->edge, edge);
    return;
}

void graph_add2edge(Graphs *graph, void *data ) {

    Graph_link *edge = graph_link_create();
    edge->value = data;
    graph_add_edge(graph, edge);
    return;
}

void graph_insert_edge(Graphs *graph, Graph_link *edge,
		 int (*cmp) (const void *, const void *)) {
    list_binsert(graph->edge, edge, cmp );
    return;
}

void graph_insert2edge(Graphs *graph, void *data,
		 int (*cmp) (const void *, const void *)) {
    Graph_link *edge = graph_link_create();
    edge->value = data;
    graph_insert_edge(graph, edge, cmp );
    return;
}

void graph_del_edge(Graphs *graph, Graph_link *link,
	       int(*ecmp)(const void *,const void *)) {
      list_bDel_key(graph->edge, link, ecmp);
      return;
   }

void graph_bDel_edge(Graphs *graph, Graph_edge *edge,
	       int(*ecmp)(const void *,const void *)) {
      list_bDel(graph->edge, edge, ecmp);
      return;
   }

void graph_sort_vertices(Graphs *graph, int(*cmp)(const void *a, const void *b)) {
   if ( listLength(graph->vertex) < PARALLELORNOT ) 
    list_qsort(graph->vertex, cmp);
   else 
    list_psort(graph->vertex, cmp);
   return;
}

void graph_sort_edges(Graphs *graph, int(* cmp)(const void *a,const void *b)) {
   if ( listLength(graph->vertex)< PARALLELORNOT ) 
    list_qsort(graph->edge, cmp);
   else
    list_psort(graph->edge, cmp);
   return;
}

void graph_final(Graphs *graph, 
	int(* vcmp)(const void *a,const void *b),
	int(* ecmp)(const void *a,const void *b)) {
     graph_sort_vertices(graph,vcmp);
     graph_sort_edges(graph,ecmp);
   return;
}

unsigned int graph_get_NodeCount(Graphs *graph) {
    return( (unsigned int)listLength((list *)graph->vertex) );
}

/*BREADTH FIRST SEARCH 
  void breadthFirstSearch(graph->vertex,void *s, int(*cmp)(void *,void *)); */
void graph_bfs(list *V,void *s, int(*gnode_cmp)(const void *,const void *))
{

        Graph_node *u; 
	
	Queue *Q;

	listIter *iter;
	Graph_node *node;

   do {

        iter=listGetIterator(V,AL_START_HEAD);
	while( (node = (Graph_node *)listNext(iter)) != NULL ) {
	     node->color = WHITE;
	     node->dist = INFI;
	     node->parent = NIL;
	}
	listReleaseIterator(iter);

	if ( (node = (Graph_node *)list_bseek_key(V,s,gnode_cmp)) == NULL ) break;

	node->color = GRAY;
        node->dist = 0;
	node->parent = NIL;
	
	Q = initQueue();
	
	enqueue(Q,s);

	while(!isQueueEmpty(Q))
	{
		u=(Graph_node *)dequeue(Q);
		
	        /*  get_edge_list();
		  for(i=0;i<V[u].out_deg;i++) */
		{
		/*
			v = V[u].adj[i];

			if(V[v].color==WHITE)
			{
				V[v].color	=	GRAY;
				V[v].dist	=	V[u].dist+1;
				V[v].parent	=	u;
				
				enqueue(Q,v);
			}
			V[u].color = BLACK; */
			u ->color = BLACK;
		}
	       

	}
	
	freeQueue(Q);

   } while(0);

   return;
}
